#include <vector>
#include <map>
#include <queue>



class Hufftree {
        public:
                Hufftree(InputIterator begin, InputIterator end);
                ~Hufftree() { delete tree; }

                std::vector<int> encode(InputIterator begin, InputIterator end);

                std::vector<int> encode(DataType const& value)
                {
                        return encoding[value];
                }

                std::vector<int> decode(std::vector<bool> const& v, OutputIterator iter);

        private:
                class Node;
                Node* tree;

                typedef std::map<DataType, std::vector<bool> > encodemap;
                encodemap encoding;

                class NodeOrder;

};


struct Hufftree<DataType, Frequency>::Node
{
        Frequency frequency;
        Node* leftChild;
        union
        {
                Node* rightChild; // if leftChild != 0
                DataType* data;  // if leftChild == 0
        };

        Node(Frequency f, DataType d):
                frequency(f),
                leftChild(0),
                data(new DataType(d))
        {
        }

        Node(Node* left, Node* right):
                frequency(left->frequency + right->frequency),
                leftChild(left),
                rightChild(right)
        {
        }

        ~Node() {
                if (leftChild) {
                        delete leftChild;
                        delete rightChild;
                } else {
                        delete data;
                }
        }

        void fill(std::map<DataType, std::vector<bool> >& encoding,
                        std::vector<bool>& prefix)
        {
                if (leftChild)
                {
                        prefix.push_back(0);
                        leftChild->fill(encoding, prefix);
                        prefix.back() = 1;
                        rightChild->fill(encoding, prefix);
                        prefix.pop_back();
                }
                else
                        encoding[*data] = prefix;
        }

};

template<typename DataType, typename Frequency>
template<typename InputIterator>
Hufftree<DataType, Frequency>::Hufftree(InputIterator begin,
                InputIterator end):
        tree(0)
{
        std::priority_queue<Node*, std::vector<Node*>, NodeOrder> pqueue;

        while (begin != end)
        {
                Node* dataNode = new Node(begin->second, begin->first);
                pqueue.push(dataNode);
                ++begin;
        }

        while (!pqueue.empty())
        {
                Node* top = pqueue.top();
                pqueue.pop();
                if (pqueue.empty())
                {
                        tree = top;
                }
                else
                {
                        Node* top2 = pqueue.top();
                        pqueue.pop();
                        pqueue.push(new Node(top, top2));
                }
        }

        std::vector<bool> bitvec;
        tree->fill(encoding, bitvec);

}

template<typename DataType, typename Frequency>
struct Hufftree<DataType, Frequency>::NodeOrder
{
        bool operator()(Node* a, Node* b)
        {
                if (b->frequency < a->frequency)
                        return true;
                if (a->frequency < b->frequency)
                        return false;

                if (!a->leftChild && b->leftChild)
                        return true;
                if (a->leftChild && !b->leftChild)
                        return false;

                if (a->leftChild && b->leftChild)
                {
                        if ((*this)(a->leftChild, b->leftChild))
                                return true;
                        if ((*this)(b->leftChild, a->leftChild))
                                return false;
                        return (*this)(a->rightChild, b->rightChild);
                }

                return *(a->data) < *(b->data);

        }
};

template<typename DataType, typename Frequency>
        template<typename InputIterator>
std::vector<bool> Hufftree<DataType, Frequency>::encode(InputIterator begin,
                InputIterator end)
{
        std::vector<bool> result;
        while (begin != end)
        {
                typename encodemap::iterator i = encoding.find(*begin);
                result.insert(result.end(), i->second.begin(), i->second.end());
                ++begin;
        }
        return result;
}

template<typename DataType, typename Frequency>
        template<typename OutputIterator>
void Hufftree<DataType, Frequency>::decode(std::vector<bool> const& v,
                OutputIterator iter)
{
        Node* node = tree;
        for (std::vector<bool>::const_iterator i = v.begin(); i != v.end(); ++i)
        {
                node = *i? node->rightChild : node->leftChild;
                if (!node -> leftChild)
                {
                        *iter++ = *(node->data);
                        node = tree;
                }
        }
}


